`
https://leetcode.cn/problems/minimum-insertion-steps-to-make-a-string-palindrome/
`

/**
 * @param {string} s
 * @return {number}
 */
var minInsertions = function (s) {
  // 先算出字符串 s 中的最长回文子序列，那些不在最长回文子序列中的字符，就是需要插入的字符
  // https://leetcode.cn/problems/longest-palindromic-subsequence/
  return s.length - longestPalindromeSubseq(s)
};

var longestPalindromeSubseq = function (s) {
  const n = s.length
  const dp = new Array(n).fill(0)
  for (let i = n - 1; i >= 0; i--) {
    dp[i] = 1
    let pre = 0
    for (let j = i + 1; j < n; j++) {
      let temp = dp[j]
      if (s[i] === s[j]) {
        dp[j] = pre + 2
      } else {
        dp[j] = Math.max(dp[j - 1], dp[j])
      }
      pre = temp
    }
  }
  return dp[n - 1]
};